#include <deque>
#include <vector>
#include <string>
#include <cstring>
#include <fstream>
#include <iostream>
#include <algorithm>

#include "syn.hpp"

using namespace std;

bool Syn::able_infer_to_empty(const string &sym) {
	if (empty_map.find(sym) != empty_map.end()) { // sym已推导过
		return empty_map[sym];
	}

	if (VT.find(sym) != VT.end()) { // sym为终结符
		bool res = sym == "$";
		empty_map[sym] = res;
		return res;
	}

	for (auto iter = produce.begin(); iter != produce.end(); ++iter) {
		if ((*iter).first == sym) { // 找到sym的推导式
			vector<string> &items = (*iter).second;
			int cnt;
			for (cnt = 0; cnt < items.size(); ++cnt) {
				if (!(this->able_infer_to_empty(items[cnt]))) { // 产生式右边存在项不能推导出空字符
					break;
				}
			}
			if (cnt == items.size()) { // 产生式右边所有项都能推导出空字符
				empty_map[sym] = true;
				return true;
			}
		}
	}

	// 遍历所有sym的推导式，仍不能推导出空字符
	empty_map[sym] = false;
	return false;
}

void Syn::infer_empty_map() {
	for (auto iter = symbols.begin(); iter != symbols.end(); ++iter) {
		this->able_infer_to_empty(*iter);
	}
}

void Syn::print_empty_map() {
	cout << "Empty map:" << endl;
	for (auto iter = symbols.begin(); iter != symbols.end(); ++iter) {
		cout << *iter << " => " << (empty_map[*iter] ? "true" : "false") << endl;
	}
	cout << endl;
}

unordered_set<string> Syn::get_first_set(const string &sym) {
	if (first_set.find(sym) != first_set.end()) { // sym的first集已经推导过了
		return first_set[sym];
	}

	if (VT.find(sym) != VT.end()) { // sym为终结符
		unordered_set<string> first;
		first.insert(sym);
		first_set[sym] = first;
		return first;
	}

	unordered_set<string> res;
	for (auto iter = produce.begin(); iter != produce.end(); ++iter) {
		if ((*iter).first == sym) { // 找到sym的推导式
			vector<string> &items = (*iter).second;
			int cnt;
			for (cnt = 0; cnt < items.size(); ++cnt) {
				auto firsts = get_first_set(items[cnt]);
				for (auto i = firsts.begin(); i != firsts.end(); ++i) {
					res.insert(*i);
				}
				if (!empty_map[items[cnt]]) { // 产生式右边项不能推导出空字符
					break;
				}
			}
			if (cnt == items.size()) { // 所有项都遍历完，说明所有项都能推导出空字符
				res.insert("$"); // 将空字符加入到sym的first集
			}
		}
	}
	first_set[sym] = res;
	return res;
}

void Syn::infer_first_set() {
	// 推导First集需要首先推导各符号是否能推导出空字符
	if (empty_map.empty()) {
		this->infer_empty_map();
	}
	for (auto iter = symbols.begin(); iter != symbols.end(); ++iter) {
		this->get_first_set(*iter);
	}
}

void Syn::print_first_set() {
	cout << "First Sets:" << endl;
	for (auto iter = symbols.begin(); iter != symbols.end(); ++iter) {
		cout << *iter << " => ";
		auto first_syms = first_set[*iter];
		for (auto i = first_syms.begin(); i != first_syms.end(); ++i) {
			cout << *i << " ";
		}
		cout << endl;
	}
	cout << endl;
}
